/**
 * Calculate the shannon entropy.
 * 
 * @param dataSet the data set.
 * @return shannon entropy.
 */
function calcShannonEntropy(dataSet) {
  var labelCounts = dataSet.reduce(function (labelCounts, featVec) {
    var currentLabel = featVec[featVec.length - 1];
    if (!labelCounts[currentLabel]) {
      labelCounts[currentLabel] = 0;
    }
    labelCounts[currentLabel] += 1;
    return labelCounts;
  }, {});
  return Object.keys(labelCounts).map(function (label) {
    var prob = labelCounts[label] / dataSet.length;
    return prob * (Math.log(prob) / Math.log(2));
  }).reduce(function (memo, current) {
    return memo - current;
  }, 0.0);
}

exports.calcShannonEntropy = calcShannonEntropy;

/**
 * Calculate the information gain of the each attribute in dataset.
 * 
 * @param dataSet the data set.
 * @return a list of information gain corresponding to attributes.
 */
function calcInfoGains(dataSet) {
  var ret = [];
  var baseEnt = calcShannonEntropy(dataSet);
  for (var i=0; i<dataSet[0].length-1; i++) {
    var values = Object.keys(dataSet.reduce(function (memo, featVec) {
      memo[featVec[i]] = 1;
      return memo;
    }, {}));
    var infoGain = values.map(function(val) {
      var subDataSet = splitDataSet(dataSet, i, val);
      var prob = subDataSet.length / dataSet.length;
      return prob * calcShannonEntropy(subDataSet);
    }).reduce(function(memo, current) {
      return memo - current;
    }, baseEnt);
    ret.push({
      values: values,
      infoGain: infoGain,
      attr: i
    });
  }
  return ret;
}

exports.calcInfoGains = calcInfoGains;

/**
 * Split the dataset according to the axis and the value.
 * 
 * @param dataSet the data set.
 * @param axis the attribute to compare and remove.
 * @param value the value to compare.
 * @return the sub data set without the axis feature.
 */
function splitDataSet(dataSet, axis, value) {
  return dataSet.filter(function (featVec) {
    return featVec[axis] == value;
  }).map(function (featVec) {
    return featVec.filter(function (it, i) {
      return i != axis;
    });
  });
}

exports.splitDataSet = splitDataSet;

/**
 * Majority Count wins.
 * 
 * @param classList the list of class labels.
 */
function majorityCnt(classList) {
  var count = classList.reduce(function (memo, current) {
    if (!memo[current]) {
      memo[current] = 0;
    }
    memo[current] += 1;
    return memo;
  }, {});
  return Object.keys(count).reduce(function (best, current) {
    return count[best] > count[current] ? best : current;
  }, 0);
}

exports.majorityCnt = majorityCnt;

/**
 * Sort the feature vector to a leaf node of a decision tree.
 * 
 * @param tree the decision tree.
 * @param featVec the feature vector.
 * @return the leaf node.
 */
function sortToLeaf(tree, featVec) {
  if (tree.branch) {
    var branchVal = featVec[tree.attr];
    var branch = tree.branch[branchVal];
    if (branch) {
      return sortToLeaf(branch, featVec);
    }
  }
  return tree;
}

exports.sortToLeaf = sortToLeaf;

function createDataSet() {
  return [[1, 1, 'yes'],
          [1, 1, 'yes'],
          [1, 0, 'no'],
          [0, 1, 'no'],
          [0, 1, 'no'],
          [1, 0, 'yes']];
}

exports.createDataSet = createDataSet;